package zhengqc.graph.algorithm;


import zhengqc.graph.data_structure.Graph;
import zhengqc.queue.LoopQueue;
import zhengqc.queue.Queue;

import java.util.ArrayList;

/* 适用于有向图 */
public class TopologicalSort {
    private Graph graph;
    private ArrayList<Integer> order;
    private boolean hasCycle;

    public TopologicalSort(Graph graph) {
        this.graph = graph;
        this.order = new ArrayList<>();
        this.hasCycle = false;

        if (!graph.isDirected()) {
            throw new IllegalArgumentException("ERR");
        }
        order = new ArrayList<>();
        int[] inDegrees = new int[graph.getV()];
        Queue<Integer> queue = new LoopQueue<>();
        for (int v = 0; v < graph.getV(); ++v) {
            inDegrees[v] = graph.getInDegree(v);
            if (inDegrees[v] == 0) {
                queue.enqueue(v);
            }
        }
        while (!queue.isEmpty()) {
            int cur = queue.dequeue();
            order.add(cur);
            for (int next: graph.getAdjacency(cur)) {
                inDegrees[next] -= 1;
                if (inDegrees[next] == 0) {
                    queue.enqueue(next);
                }
            }
        }
        if (order.size() != graph.getV()) {
            hasCycle = true;
            order.clear();
        }
    }
    public ArrayList<Integer> getOrder() {
        return order;
    }

    public boolean hasCycle() {
        return hasCycle;
    }
}
